//
// Created by zhuanding on 2023/6/20.
//

#ifndef DATA_STRUCTURE_NOTES_ALGRAPH_H
#define DATA_STRUCTURE_NOTES_ALGRAPH_H

#define MaxVertexNum 100 // 顶点数目的最大值
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType;  // 带权图中边上权值的数据类型
typedef int InfoType;
typedef struct ArcNode {  // 边表结点
    int adjvex;   // 该弧所指向的顶点位置
    struct ArcNode *next;  //  指向下一条弧的指针
    // InfoType info;   // 网的边权值
} ArcNode;
typedef struct VNode {   // 顶点表结点
    VertexType data;  // 顶点信息
    ArcNode *first;  // 指向第一条依附于该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum;  // 图的顶点数和弧数
} ALGraph;  //


bool Adjacent(G, x, y);  // 判断图G是否存在(x,y)或<x,y>
void Neighbors(G, x);  // 列出图G中与结点x邻接的边
bool InsertVertex(G, x); // 在图G中插入顶点x
bool DeleteVertex(G, x);   // 在图G中删除顶点x
bool AddEdge(G, x, y);  // 在图G顶点x和顶点y之间添加一条边
bool RemoveEdge(G, x, y);  // 在图G顶点x和顶点y之间删除一条边
int FirstNeighbor(G, x);  // 求图G中顶点x的第一个邻接点，若有则返回顶点好，没有或顶点x不存在则返回-1
int NextNeighbor(G, x, y);   // 假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int GetEdgeValue(G, x, y);  // 获取图G中边(x,y)或<x,y>的权值
bool SetEdgeValue(G, x, y, v);  // 设置图G中边(x,y)或<x,y>的权值


/*邻接矩阵的广度遍历算法*/
bool visited[MAX_VERTEX_NUM];  // 访问标记数组
void BFSTraverse(MGraph G) {
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVertexes; i++) {
        visited[i] = FALSE;   // 访问标记数组初始化
    }
    InitQueue(&Q);    //初始化一辅助用的队列
    for (i = 0; i < G.numVertexes; i++) {
        //若是未访问过就处理
        if (!visited[i]) {
            vivited[i] = TRUE;    //设置当前访问过
            visit(i);    //访问顶点
            EnQueue(&Q, i);    //将此顶点入队列
            //若当前队列不为空
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);    //顶点i出队列
                //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
                //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
                for (j = FirstNeighbor(G, i); j >= 0; j = NextNeighbor(G, i, j)) {
                    //检验i的所有邻接点
                    if (!visited[j]) {
                        visit(j);    //访问顶点j
                        visited[j] = TRUE;    //访问标记
                        EnQueue(Q, j);    //顶点j入队列
                    }
                }
            }
        }
    }
}


#define INF 0x3f3f3f3f   // INF表示无穷

void BFS_MIN_Distance(Graph G, int u) {
    // BFS求解单源最短路径问题
    // d[i]表示从u到i结点的最短路径
    for (int i = 0; i < G.vexnum; ++i)
        d[i] = INF;  // 初始化路径长度
    visited[u] = true;
    d[u] = 0;
    Enqueue(Q, u);
    while (!isEmpty(Q)) {   // BFS算法主过程
        Dequeue(Q, u);    // 队头元素u出队
        for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            if (!visited[w]) {   // w为u的尚未被访问的邻接顶点
                visited[w] = true;  // 设已访问标记
                d[w] = d[u] + 1;  // 路径长度加1
                Enqueue(Q, w);  // 顶点w入队
            }
        }
    }
}




#endif //DATA_STRUCTURE_NOTES_ALGRAPH_H
